The present invention relates to the field of autonomous vehicles, and more particularly to a system for controlling multiple autonomous vehicles from a single host station.
A wide variety of techniques have been developed to effectuate navigation of autonomous guided vehicles. Such techniques may be grouped into three general categories: (1) guidepath following; (2) unrestricted path planning; and (3) virtual path navigation.
The simplest form of navigational control of an autonomous guided vehicle is referred to as guidepath following which involves a navigational control loop which reflexively reacts to the sensed position of some external guiding reference. In industry, autonomous guided vehicles have been guided by physical paths including slots, buried wires, optical stripes, and other methods for almost thirty years. Such automated guided vehicles have found extensive use in factories and warehouses for material transfer, in modern office scenarios for material and mail pickup and delivery, and in hospitals for delivery of meals and supplies to nursing stations.
The most common guidepath following schemes in use today involve some type of stripe or wire guidepath permanently installed on the floor of an operating area. Specialized sensors on the front of an autonomous guided vehicle are used to servo-control the steering mechanism, causing the vehicle to follow a route defined by the guidepath. Guidepath schemes can be divided into three general categories: (1) those which sense and follow the AF or RF field from a closed-loop wire embedded in the floor; (2) those which sense and follow a magnetic tape in or on the floor; and (3) those which optically sense and follow some type of stripe affixed to the floor surface.
Implementations of the stripe following method include the most simplistic case of tracking a high contrast (dark-on-light, light-on-dark) line. More advanced optical systems have been developed which track a special reflective tape illuminated by a near-infrared source, and a chemical stripe which glows when irradiated by ultraviolet energy.
Advantages of guidepath control are seen primarily in the improved efficiency and reduction of manpower which arise from the fact that an operator is no longer required to guide the vehicle. Large numbers of autonomous guided vehicles can operate simultaneously in a plant or warehouse without getting lost or disoriented, scheduled and controlled by a central computer which monitors overall system operation vehicle flow. Communication with individual vehicles may be effectuated using radio frequency links or directional near-infrared modulated light beams, or by other means.
The fundamental disadvantages of guidepath control are the cost of path installation and maintenance, and the lack of flexibility in the system. A vehicle cannot be commanded to go to a new location unless the guidepath is first modified. This is a significant disadvantage when changes to product flow lines and assembly plants or, in the case of a security robot which must investigate a potential break-in at a designated remote location, that is not on the guidepath.
Another type of navigational control system for autonomous guided vehicles is one that uses unrestricted path planning. In this type of system a free-roaming vehicle may be directed anywhere subject to nominal considerations of terrain topography. Many potential applications await an autonomous guided vehicle that could move in a purposeful fashion without following a set guidepath, with the intelligence to avoid objects and if necessary choose alternative routes of its own planning. Most of the path planning to date has been done on the premise that the ultimate navigation system would be capable of mapping out its environment with sensors and then planning routes accordingly. While such systems have a great deal of appeal, they encounter several significant difficulties in practice.
The most significant problem associated with building a world model to support a navigation system employing unrestricted path planning is the poor quality of most sensor data. There are many choices available to the designer of such a navigation system but in every case good data is expensive. In practice, reflective sensors such as ultrasonic range finders and near-infrared proximity detectors have predominated. However, all reflective sensors are subject to the problems of noise, specular and secondary reflections and signal absorption to one extent or another.
Of all the data provided from a sensor system at a given location, only a small percentage is true, pertinent, and accurate. Furthermore, the position of objects viewed from different positions will be distorted by any errors in the vehicle's dead reckoning accuracy as it moves between vantage points. Template matching of sensor data can thus be very difficult. Finally, there are areas that appear clear to sensors which may in fact may be dangerous or impassible for other reasons. Such impasses place additional data editing responsibilities on the vehicle's programmer.
Specialized sensors must be coupled with some type of world modeling capability in order to provide a model vehicle with sufficient awareness of its surroundings to support intelligent movement in unstructured environments. "World modeling" is a well known phrase in the art which refers to numerically representing an operating environment. The model represents a two-dimensional mapping of the absolute locations of surrounding objects, and is refined in a continuous fashion as the vehicle moves about its work space. The accuracy of this model is directly dependent upon the validity of the vehicle's own perceived location and orientation. Accumulated dead reckoning errors soon render the data entered into the model invalid and that the associated geographical reference point for data acquired relative to the vehicle's position is incorrect.
As the accuracy of the model degrades, the ability of the vehicle to successfully navigate and avoid collisions diminishes rapidly, until it fails altogether. A robust navigational scheme that preserves the validity of the world model for free-roaming vehicles employing unrestricted path planning navigation systems has remained an elusive research goal and for this reason many proposed applications of truly autonomous vehicles are as yet to be implemented.
Providing an autonomous capability to support non-unrestricted motion, therefore, involves the implementation of an appropriate map representation, the acquisition of data regarding ranges and bearings to nearby objects, and the subsequent interpretation of that data in building and maintaining the world model.
Several different map representation schemes have been devised to construct a world model, including polyhedra objects, generalized cones, certainty grids, and quadrees. The simplest scheme is a two-dimensional array of cells used to define an environment. Each cell corresponds to a square of fixed size in the region being mapped. The map can be accessed and updated quickly, which is extremely important for real-time operation. Free space is indicated with a cell value of zero; a non-zero cell value indicates an object. The most compact form of a cell map consists of one bit per cell, and thus indicates only the presence or absence of an object. By using multiple bits per cell, additional descriptive data can be represented in the map such as identification of structural walls and doorways. In addition, the probability of a given square being occupied can be easily encoded, which turns the map into a form of a certainty grid. This statistical approach is especially useful when the precise location of object is unknown.
One type of unrestricted path planning navigational system uses a search algorithm that begins by "expanding" the initial cell corresponding to the robot's current position in the floor map (i.e., each unoccupied neighbor cell is added to the "expansion list."). Each cell on the expansion list is expanded. The cell expansion process continues until the destination cell is placed on the expansion list, or the list becomes empty, in which case no path exists. This algorithm will find the minimum distance path from the initial position of the vehicle to the destination.
However, the minimal distance path is not necessarily the best path. Sometimes it is more desirable to minimize the number of turns of the vehicle to reach its destination, or to maximize the distance from certain obstacles. A cell expansion search type strategy can be altered accordingly by assigning a cost to each cell prior to adding it to the expansion list. Only the minimum cost cells are then expanded. This is known in the literature as an A* search which is noted to have inherent flexibility associated with the cost function.
Another type of navigational system for autonomous vehicles employs a virtual path concept developed by Cybermotion, Inc. of Roanoke, Va. to provide a routine mechanism for correcting dead reckoning errors and a normal course of path execution. Each desired route, or path is preprogrammed by a technician to take advantage of any available environmental queues that the robot can recognize with its sensors. An environmental queue may be a wall, floor stripe, support column, or other feature at a particular location in the environment having coordinates which may be used as a benchmark, or reference for navigational purposes. Each path begins and ends on named virtual node. A database is constructed that associates each virtual note with one or more virtual path segments entering or leaving that location. Several discrete path segments may be linked together to form a complete virtual path from any given node to any other node.
Correction of dead reckoning errors accumulated as the vehicle executes a path is commonly accomplished by indicating in the virtual path program one or both of the following queues: the distance to walls on the left or right side of the robot and the expected stand-off of the wall in front of the robot at the completion of the route segment.
In the wall-following mode, the autonomous vehicle of the type described in U.S. Pat. No. 5,111,401, entitled "Navigational Control System for an Autonomous Vehicle", uses its lateral sonars to maintain a specified offset from the detected wall while traversing the distance between two given points. Knowing the starting and ending locations of the virtual path segment enables the robot to correct its heading as well as a lateral access position coordinate. When approaching a wall, the autonomous vehicle uses forward sonars to measure its actual distance from the wall. By comparing the observed range with anticipated distance specified in the program, and knowing the X-Y coordinate of where the vehicle should be when it stops, the autonomous vehicle can correct the longitudinal coordinate of its dead reckoned position. When wall following and wall approach are used on the same path segment, both the X and Y coordinates can be corrected, as well as the heading of the vehicle.
Although the virtual path approach does not provide the flexibility of unrestricted path planning, the virtual path approach may be implemented with relatively low cost sensor and computing hardware. Moreover, the virtual path approach is more adaptable than guidepath following alone. Many practical applications can be addressed with this method, but it suffers from a fundamental deficiency in the lack of collision avoidance capability. If an obstacle blocks a virtual path route segment, the autonomous vehicle must halt and wait for further directions.
In order to overcome the deficiencies in the aforementioned navigational systems, a hybrid navigational control system for an autonomous vehicle was developed, as is described in U.S. Pat. No. 5,111,401, entitled "Navigational Control System for an Autonomous Vehicle". The navigational system described in the '401 patent employs a hybrid navigational scheme which exploits the inherent re-referencing ability of the virtual path system, while retaining the free roaming flexibility of unrestricted path planning control. Under normal conditions an autonomous vehicle of the type identified above generally navigates using the hybrid navigational scheme traverses virtual paths which are kept relatively obstacle-free. Such traversal may be made at significantly higher speeds than are typically possible for autonomous vehicles navigating using the conventional unrestricted path system. In the event of an impending collision between the vehicle and some other object, the vehicle is halted and an avoidance maneuver around the obstacle is planned and implemented so that the vehicle may proceed to the desired virtual point of destination. Another type of hybrid navigational control system for an autonomous vehicle which is commercially available is known as the Cybermotion Virtual Path Navigation Scheme, which is generally provided with the Model K2A or K3A NAVMASTER autonomous guided vehicle platform by Cybermotion, Inc. There are many applications for autonomous vehicles, such as in providing security for large warehouses or in military installations, in which one vehicle is not able to provide sufficient security, whereas multiple autonomous vehicles roaming throughout such environments would. However, the problems of control and coordination of multiple autonomously guided vehicles are significant. For example, such a control system must be able to simultaneously direct multiple autonomously guided vehicles along individual paths in the operating environment while directing other vehicles around obstacles. Further, such system should also have the capability of allowing direct human supervisory control of an autonomous vehicle for situations where a particular vehicle becomes blocked in its path or inoperable. Resources for determining virtual, unrestricted, and obstacle avoidance paths, and for providing direct human supervisory control of an autonomous vehicle should be allocated on an as needed basis in order to minimize the equipment required to implement such a system. Therefore, there is a need for a system that can control the operation of multiple autonomous vehicles operating within an environment that addresses the above-referenced needs.
The control systems described in the '401 patent and used in conjunction with the Cybermotion NAVMASTER K2A or K3A autonomous vehicle platforms requires one dedicated computer for each deployed autonomous guided vehicle. In such a system, referred to as a "dedicated" system", each computer provides path planning and obstacle avoidance capabilities, as well as an operator station for direct teleoperated control of a vehicle by a human operator, such as described in U.S. Pat. No. 5,307,271, "Reflexive Teleoperated Control System For A Remotely Controlled Vehicle." For example, if it is desired to deploy ten autonomous guided vehicles, a dedicated system requires that there be ten computer/operator stations. However, a human operator is generally only capable of controlling one autonomous vehicle at a time. Therefore, dedicated system in which situations requiring simultaneous real-time human intervention for multiple vehicles would tend to overwhelm a human operator with information overload. For example, if a guard is currently teleoperating a vehicle 19, he may be unaware that one of the other vehicles 19 has detected an intruder because he is unable to see the display for that computer from his current location. In addition, having a computer monitor and user interface dedicated to each vehicle 19 requires a significant amount of desk space, which is usually at a premium in typical control rooms. Because dedicated systems are inherently unwieldy and complicated, there is a need for a more manageable system for controlling multiple autonomous vehicles.
In the '401 and Cybermotion systems, path planning and obstacle avoidance solutions are typically downloaded from a host computer (general purpose digital data processor) to a local processor on board the autonomous guided vehicle. The local processor then directs control of the vehicle. However, the generation of such solutions typically requires very little processing time by the host computer. Therefore, dedicated systems tend to be resource inefficient, and hence expensive, in terms of idle host computer time. A more efficient solution for the control of multiple autonomous vehicles would allow multiple autonomous vehicles to share host computer and operator station resources. Therefore, there is a further need for a more efficient system for controlling multiple autonomous vehicles which allocates system resources on an "as needed" basis.